Haskell でアルゴリズムを抽象化する〜関数型言語で競技プログラミング

今回で発表したことは最初から知っていたわけではなく、アルゴリズムを Haskell で実装する中で発見してきた

アルゴリズムを抽象化すると、その実装が似たようなインタフェースとなる

競技プログラミングではあらかじめアルゴリズムをライブラリ化（抽象化）しておくことが多い

具体的には写像（map）と結合（fold）の二項演算がパラメータとして現れる

写像: 各状態を新しい状態に移す

結合: 複数の結果を 1 つにまとめる

当初はグラフにのみ対応した実装であった

しかし、状態遷移の写像をパラメータとして受け取ることで様々な問題に応用できるようになった

BFS も半環でモナドらしい ??

DP を解くには 2 次元配列で考えることが多い

https://gyazo.com/da5d9fff053492f0e9a651c4a20c310d

命令型では可変な二次元配列を用意する必要がある

しかし、次元数が増えていくほど頭が混乱する

https://gyazo.com/c668be54f9e505ce8af54fbad878bc92

そのため、状態空間（行）が次の状態に遷移すると考えれば良い

https://gyazo.com/4b26f40ff30e19c2af376b46dcfcf3dd

これは fold で実現できる

インタフェースを見ると、DP は半環的構造を持つ

https://gyazo.com/a50d554fceda23d7b99e4a7dc54371e8

BFS も同様 ?

なぜ map と reduce で問題が解けるか？

再帰的データ構造（ADT）をデータ構造の基本としている: data List a = Nil | Cons a (List a)

再帰的データ構造に適した最小の操作が map と reduce（fold）

map: 再帰構造に対する関数適用の最小単位

reduce: 再帰構造を畳み込むパターンの最小単位

map と reduce はどこから来たのか

Lisp がリストに対する map / reduce で多くの問題を記述できることを経験則的に発見

FPL の発展により、他のデータ構造にも適用されるようになった

Haskell がそれらを理論付け、型クラス階層とともに取り込んだ

命令型でアルゴリズムを書く場合: 「どう動かすか」に焦点を当てる

https://gyazo.com/9a83c550c1b6966cae75f9689daa26df

関数型でアルゴリズムを書く場合: 「なにを意味しているか」に焦点を当てる

https://gyazo.com/e697abf411742af54dac5ac94cc11fe1